/* Sorted double linked list.

   This file is part of khipu.

   khipu is free software: you can redistribute it and/or modify
   it under the terms of the GNU Lesser General Public License as published by
   the Free Software Foundation; either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public License
   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */

#ifndef __UTILS_SORTED_LIST__
#define __UTILS_SORTED_LIST__   1

#include "../memory.hpp"

KP_DECLS_BEGIN

struct basic_cmp
{
  int operator() (intptr_t left, intptr_t right) const
    {
      return ((int)(left - right));
    }
};

struct sorted_list_base
{
  struct node
    {
      node *prev;
      node *next;
      intptr_t key;
      intptr_t val;
    };
    
  node root;
  
  struct iterator
    {
      node *runp;
      node *endp;
      
      iterator (sorted_list_base& sl) :
          runp (sl.root.next), endp (&sl.root)
        {
        }

      iterator (node *rp, sorted_list_base& sl) :
          runp (rp), endp (&sl.root)
        {
        }
      
      bool valid () const
        {
          return (this->runp != this->endp);
        }

      iterator& operator++ ()
        {
          this->runp = this->runp->next;
          return (*this);
        }

      iterator operator++ (int)
        {
          iterator ret = *this;
          ++*this;
          return (ret);
        }
        
      intptr_t& key ()
        {
          return (this->runp->key);
        }
        
      intptr_t& val ()
        {
          return (this->runp->val);
        }

      node*& link ()
        {
          return (this->runp);
        }

      const node* link () const
        {
          return (this->runp);
        }
    };
  
  sorted_list_base ()
    {
      this->root.key = this->root.val = 0;
      this->root.prev = this->root.next = &this->root;
    }
    
  node* insert (node *pos, intptr_t key, intptr_t val)
    {
      node *tmp = (node *)xmalloc (sizeof (*tmp));
      tmp->key = key, tmp->val = val;
      
      pos->next->prev = tmp;
      tmp->prev = pos;
      tmp->next = pos->next;
      pos->next = tmp;
      
      ++this->root.key;
      return (tmp);
    }

  void add_end (intptr_t key, intptr_t val)
    {
      this->insert (this->root.prev, key, val);
    }

  void erase (node *pos)
    {
      pos->prev->next = pos->next;
      pos->next->prev = pos->prev;
      --this->root.key;
      xfree (pos);
    }

  void swap (sorted_list_base& sl)
    {
      auto adj = this->root.prev;
      adj->next = adj->prev = &sl.root;

      adj = sl.root.prev;
      adj->next = adj->prev = &this->root;

      auto tmp = this->root;
      this->root = sl.root, sl.root = tmp;
    }

  uint32_t len () const
    {
      return ((uint32_t)this->root.key);
    }

  ~sorted_list_base ()
    {
      for (node *runp = this->root.next; runp != &this->root; )
        {
          node *tmp = runp->next;
          xfree (runp);
          runp = tmp;
        }

      this->root.prev = this->root.next = &this->root;
      this->root.key = 0;
    }
};

template <class Cmp = basic_cmp>
struct sorted_list : public sorted_list_base
{
  Cmp cmp;

  node* add (intptr_t key)
    {
      node *runp;
      for (runp = this->root.next; runp != &this->root; runp = runp->next)
        {
          int c = this->cmp (runp->key, key);
          if (c == 0)
            return (runp);
          else if (c > 0)
            break;
        }

      return (this->insert (runp->prev, key, -1));
    }
    
  bool add (intptr_t key, intptr_t val)
    {
      node *runp;
      for (runp = this->root.next;
          runp != &this->root; runp = runp->next)
        {
          int c = this->cmp (runp->key, key);
          if (c == 0)
            {
              runp->val = val;
              return (false);
            }
          else if (c > 0)
            break;
        }
        
      this->insert (runp->prev, key, val);
      return (true);
    }
    
  intptr_t get (intptr_t key, intptr_t dfl) const
    {
      for (node *runp = this->root.next;
          runp != &this->root; runp = runp->next)
        {
          int c = this->cmp (runp->key, key);
          if (c == 0)
            return (runp->val);
          else if (c > 0)
            break;
        }
          
      return (dfl);
    }
    
  iterator find (intptr_t key)
    {
      for (node *runp = this->root.next;
          runp != &this->root; runp = runp->next)
        {
          int c = this->cmp (runp->key, key);
          if (c == 0)
            return (iterator (runp, *this));
          else if (c > 0)
            break;
        }

      return (iterator (&this->root, *this));
    }
};

KP_DECLS_END

#endif
